Search results for "dinamiskā programmēšana"
showing 5 items of 5 documents
Izejvielu aprites optimizācija ražošanas uzņēmumā, lietojot dažādus krājuma vadības modeļus
2017
Darba mērķis ir atrast modeli, kuru varētu izmantot kā pilnvērtīgu rīku, kas palīdzētu optimizēt izejvielu un iepakojumu iegādi. Darbā tiek apskatīti trīs modeļi, pirmie divi tika veidoti balstoties uz literatūru un trešais tika izveidots paša spēkiem, izmantojot iegūtās zināšanas lineārajā programmēšanā.
Laika-atmiņas kompromisi eksponenciālā laika kvantu algoritmiem
2021
Arvien vairāk uzdevumiem tiek izgudroti kvantu algoritmi, kas ir pārāki pār labākajiem zināmajiem klasiskajiem algoritmiem. Bieži šiem algoritmiem nepieciešamais atmiņas daudzums ir liels, kas pašlaik mazās pieejamās kvantu atmiņas dēļ nav optimāli. Tādēļ ir būtiski apskatīt algoritmus, kuru atmiņas sarežģītība ir samazināta, palielinot laika sarežģītību, bet kas vēl aizvien sniedz uzlabojumu pār klasiskajiem algoritmiem. Viens no šādiem uzdevumiem ir algoritms ceļa atrašanai hiperkubā, kuram 2019. gadā atrasts kvantu algoritms ar laika un atmiņas sarežģītību $\widetilde O(1.817^n)$. Šis uzdevums ir interesants, jo ar tā palīdzību var modelēt daudzas NP-pilnas problēmas, šādi tās atrisinot …
Zemkvadrātisks algoritms koku ceļu apakšvirkņu uzdevumam
2021
Darbā tiek apskatīts garākās kopīgās apakšvirknes uzdevuma vispārinājums uz kokiem. Tiek apskatīti divi vienāda izmēra koki, kuru virsotnes ir marķētas ar vienas kopas elementiem. Garākā kopīgā apakšvirkne tiek meklēta pāri visiem ieejas koku ceļu pāriem. Galvenais rezultāts ir algoritms, kas risina apskatīto uzdevumu laikā $O(n \log^3 n)$, kur $n$ ir abu ieejas koku virsotņu skaits.
Kvantu algoritmi grafa koka platumam
2021
Grafu teorijā koka platums ir ar neorientētu grafu asociēts skaitlis. Vairākas NP-pilnas problēmas grafiem var būt atrisinātas polinomiālajā laikā pie nosacījuma, ka grafa koka platums ir ierobežots. Koka platuma rēķināšana ir pats par sevi NP-pilns uzdevums, un labākajam zināmajam klasiskajam algoritmam, kas to risina, ir sarežģītība $O^*(1.7347^n)$. Šajā darbā ir iegūts kvantu algoritms koka platumam ar sarežģītību $O^*(1.6683^n)$.
Kvantu vaicājumu sarežģītība dinamiskās programmēšanas problēmām
2022
Dinamiskā programmēšana (DP) ir plaši pētīta no klasiskās skaitļošanas puses, un jauni rezultāti tiek atrasti katru gadu. Taču no kvantu skaitļošanas puses tā ir pētīta daudz mazāk. Tāpēc tika izvēlētas un pētītas vairākas plaši pazīstamas 1-dimensiju DP problēmas, izmantojot kvantu vaicājumu modeli. Darbā tika aplūkotas mazākā svara apakš-sekvences (LWS) problēmas, kā, piemēram, kastu komplektēšanas (NestedBoxes) problēma, kā arī dažas saistītās problēmas. Darba mērķis bija atrast aplūkotajām LWS problēmām augšējo novērtējumu, kas labāks par triviālo O ̃(n^1.5 ) vai labu apakšējo novērtējumu. Izdevās atrast vairākus mazākus rezultātus NestedBoxes problēmai – kvantu apakšējo novērtējumu Ω(n…